package GaTsp;

import java.util.ArrayList;
import java.util.Arrays;

import com.demosL1.demo05.Main;

public class GA_TSP {
	static float Pbest = 0.6F;
	public static void main(String[] args) {
		//先将城市信息录入矩阵
		int size = 100;
		int max = 500;//点的坐标落在0~50
		int[][] info = new int[size][2];//表示0~99号城市的x,y值
		int poluNumber = 50;//50个染色体
		int[][] polulation = new int[poluNumber][size];//种群信息
		int[] fitNess = new int[poluNumber];//适应值
		double p_update = 0.003;//变异概率
		int number = 300;//迭代次数
		
		for(int i =0;i<size;i++) {
			info[i][0] = (int) (Math.random()*max);
			info[i][1] = (int) (Math.random()*max);
			for(int j = 0;j<i;j++) {
				while(info[i][0] == info[j][0]&&info[i][1] == info[j][1]) {
					info[i][0] = (int) (Math.random()*max);
					info[i][1] = (int) (Math.random()*max); 
				}
			}
		}
		
		int[] bestIndex = new int[(int) (size*Pbest)];//存放优秀种群的下标
		polulation = initPolu(polulation);
		System.out.print("初始化：");
		readPolu(fitNess(polulation, info));
		for(int i = 0;i<number;i++) {
			update(polulation, info, p_update);
			//更新适应值
			fitNess = copyPolu(fitNess(polulation,info));
//			System.out.println();
//			readPolu(fitNess(polulation, info));
		}
		int index = 0;
		for(int i = 1;i<polulation.length;i++) {
			if(fitNess[index]>fitNess[i]) {
				index = i;
			}
		}
		System.out.printf("\n策略：");
		readPolu(polulation[index]);
		System.out.println();
		System.out.println("路径长："+fitNess[index]);
	}
	/**
	 * 复制染色体
	 */
	private static int[] copyPolu(int[] info) {
		int[] nums = new int[info.length];
		for(int i= 0;i<nums.length;i++) {
			nums[i] = info[i];
		}
		return nums;
	}
	
	/**
	 * 更新种群
	 * @param polulation
	 * @return
	 */
	public static int[][] update(int[][] polulation,int[][] info,double p_update){
		int[][] bestPolu = new int[(int) (polulation.length*GA_TSP.Pbest)][polulation[0].length];
		int Bindex = 0;
		int Pindex = 0;
		ArrayList<Integer> list = new ArrayList<>();
		
		int[] pestPolu = getBestPolu(fitNess(polulation, info));
		Arrays.sort(pestPolu);
		for(int i = 0;i<bestPolu.length;i++) {
			list.add(pestPolu[i]);
		}
		
		while(Pindex<polulation.length&&Bindex<bestPolu.length) {
			if(!list.contains(Pindex)) {
				Pindex++;
			}else {
				bestPolu[Bindex] = copyPolu(polulation[Pindex]);
				Bindex++;
				Pindex++;
			}
		}
		
		int[][] childs = new int[(int) (polulation.length*(1-GA_TSP.Pbest))][polulation[0].length];
		for(int i = 0;i<childs.length;i++) {
			int p1 = (int) (Math.random()*bestPolu.length);
			int p2 = (int) (Math.random()*bestPolu.length);
			childs[i] = select(bestPolu[p1], bestPolu[p2]);
		}
		
		int p1 = 0;
		int c1 = 0;
		while(p1<polulation.length&&c1<childs.length) {
			if(list.contains(p1)) {
				p1++;
			}else {
				polulation[p1] = copyPolu(childs[c1]);
				p1++;
				c1++;
			}
		}
		
		double p = Math.random();
		if(p<p_update) {
			int index = (int) (Math.random()*polulation.length);
			polulation[index] = copyPolu(variation(polulation[index]));
		}
	
		return polulation;
	}
	
	/**
	 * 计算优秀种群
	 */
	private static int[] getBestPolu(int[] fitNess) {
		int[] result = new int[(int) (fitNess.length*0.6)];
		ArrayList<Integer> list = new ArrayList<>();
		for(int i = 0;i<result.length;i++) {
			int min = Integer.MAX_VALUE;
			for(int j = 0;j<fitNess.length;j++) {
				if(!list.contains(fitNess[j])&&min>fitNess[j]) {
					min = fitNess[j];
					result[i] = j;
				}
			}
			list.add(min);
		}
		return result;
	}
	
	/**
	 * 
	 * 交叉获取子代
	 * @param parent1
	 * @param parent2
	 * @return
	 */
	public static int[] select(int[] parent1,int[] parent2) {
		int begin = (int) (Math.random()*parent1.length);
		int end = (int) (Math.random()*parent1.length);
		if(begin>end) {
			int temp = begin;
			begin = end;
			end = temp;
		}
		
		int[] child = new int[parent1.length];
		
		/**
		 * 复制不变位
		 */
		ArrayList<Integer> list = new ArrayList<>();
		for(int i = begin;i<=end;i++) {
			child[i] = parent2[i];
			list.add(child[i]);
		}
		
		/**
		 * 继续交叉
		 */
		int childIndex = 0;
		int parentIndex = 0;
		while(parentIndex<parent1.length&&childIndex<parent1.length) {
			if(list.contains(parent1[parentIndex])) {
				parentIndex++;
				continue;
			}
			if(childIndex<begin||childIndex>end) {
				child[childIndex] = parent1[parentIndex];
				childIndex++;
				parentIndex++;
			}else {
				childIndex = end+1;
			}
		}
		
		return child;
		
		
	}
	
	/**
	 * 变异
	 */
	public static int[] variation(int[] parent) {
		int begin = (int) (Math.random()*parent.length);
		int end = (int) (Math.random()*parent.length);
		
		int temp = parent[begin];
		parent[begin] = parent[end];
		parent[end] = temp;
		
		return parent;
	}
	
	/**
	 * 使用曼哈顿距离计算距离
	 * @param info
	 */
	public static int getResult(int[] poluInfo,int[][] city) {
		int sum = 0;
		for(int i = 1;i<poluInfo.length;i++) {
			sum+=Math.abs(city[poluInfo[i]][0]-city[poluInfo[i-1]][0])+Math.abs(city[poluInfo[i]][1]-city[poluInfo[i-1]][1]);
		}
		sum+=Math.abs(city[poluInfo[poluInfo.length-1]][0]-city[poluInfo[0]][0])+Math.abs(city[poluInfo[poluInfo.length-1]][1]-city[poluInfo[0]][1]);
		return sum;
	}
	
	/**
	 * 初始化种群
	 */
	public static int[][] initPolu(int[][] polulation) {
		for(int i = 0;i<polulation.length;i++) {
			polulation[i] = getNotListNums(polulation[0].length);
		}
		return polulation;
	}
	
	/**
	 * 计算所有种群的适应值
	 */
	public static int[] fitNess(int[][] polulation,int[][] city) {
		int[] fitNess = new int[polulation.length];
		for(int i = 0;i<fitNess.length;i++) {
			fitNess[i] = getResult(polulation[i], city);
		}
		return fitNess;
	}
	
	/**
	 * 随机生成无序的0~size-1的数组！
	 * @param size
	 * @return
	 */
	private static int[] getNotListNums(int size) {
		int[] temp = new int[size];
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i = 0;i<size;i++) {
			int num = (int)(Math.random()*size);
			while(list.contains(num)) {
				num = (int)(Math.random()*size);
			}
			temp[i] = num;
			list.add(num);
		}
		return temp;
	}
	
	/**
	 * 查看城市信息
	 * @param info
	 */
	public static void readCity(int[][] info) {
		for(int i = 0;i<info.length;i++) {
			for(int j = 0;j<info[0].length;j++) {
				System.out.print(info[i][j]+" ");
			}
			System.out.println();
		}
	}

	/**
	 * 查看染色体信息
	 */
	public static void readPolu(int[] info) {
		for(int i = 0;i<info.length;i++) {
			System.out.print(info[i]+" ");
		}
		System.out.println();
	}
}
